package com.crl.map.utils.astar
{
	import flash.geom.Point;

	public class AstarFinder
	{
		private var openList:OpenList;
		private var closeList:XYSet;
		
		
		private var dirs:Array=[
										[-1,-1],[0,-1],[1,-1],
										[-1, 0],         [1,0],
										[-1, 1],[0, 1],[1,1]
										]
		
		private var nodeG:INodeGenerater;
		public function AstarFinder(nodeG:INodeGenerater)
		{
			this.nodeG=nodeG;
			openList=new OpenList(nodeG.getTW(),nodeG.getTH());
			closeList=new XYSet(nodeG.getTW(),nodeG.getTH());
		}
		
		public function find(sp:Point,ep:Point):Node{
			openList.clear();
			closeList.clear();
			var sx:int=sp.x;
			var sy:int=sp.y;
			var startNode:Node=nodeG.getNode(sx,sy);
			if(startNode==null){
				return null;
			}
			
			var ex:int=ep.x;
			var ey:int=ep.y;
			if(nodeG.getNode(ex,ey)==null){
				return null;
			}
			
			openList.add(startNode);
			
			
			
			var popNode:Node;
			while(true){
				popNode=openList.pop();
				if(popNode==null){
					return null;
				}
				
				closeList.add(popNode.x,popNode.y);
				
				var ox:int=popNode.x;
				var oy:int=popNode.y;
				
				
				
				for each(var dir:Array in dirs){
					var cx:int=ox+dir[0];
					var cy:int=oy+dir[1];
					var node:Node=nodeG.getNode(cx,cy);
					if(node==null){
						continue;
					}
					
					var hypotenuse:Boolean=((cx-ox)*(cy-oy) !=0);//不为0为斜边;
					var canHypo:Boolean=true;
					if(hypotenuse){
						//如果斜边相邻有方面有障碍，不允许过去;
						canHypo=(nodeG.getNode(ox,cy)!=null && nodeG.getNode(cx,oy) !=null);
					}
					
					if(canHypo==false || closeList.contains(cx,cy)){
						continue;
					}
					
					var g:int=hypotenuse ? 14:10;
					var h:int=(Math.abs(cx-ex)+Math.abs(cy-ey))*10;
					
					//如果已在打开列表中;
					if(openList.contains(node)){
						var newG:int=popNode.g+g;
						if(newG<node.g){
							node.g=newG;
							node.f=node.g+h;
							node.parent=popNode;
							node.d=(cx-sx+1)+(cy-sy+1)*3;
							openList.reset(node);
						}
						
					}else{
						node.g=popNode.g+g;
						node.f=node.g+h;
						node.parent=popNode;
						node.d=(cx-sx+1)+(cy-sy+1)*3;
						if(cx==ex && cy==ey){
							return node;
						}
						openList.add(node);
					}
					
				}
				
			}
			return null;
		}
	}
}